\documentclass[12pt,a4]{article}

\input{preamble}

\setcounter{section}{3}



\begin{itemize}
 \item Monday, 2018-03-19, homework handed out
 \item Sunday, 2018-03-25, 12:00: submit questions and first submissions. You'll get feedback
 until Wednesday.
 \item Sunday, 2018-03-29 (Wednesday), 18:00: submit your review of the other group's first submission.
 \item 2018-04-01: submit final solution.
\end{itemize}



\section{Pascal's Triangle Modulo 2}




Here are two early tables of the binomial coefficient:
\begin{center}
  \includegraphics[width=\textwidth]{figures/two-pascal-triangles.pdf}
\end{center}
Here is my version of ``Pascal's triangle'', indicating that rows are indexes by $n$ and ``columns''
by $k$:
\begin{center}
  \includegraphics[width=0.8\textwidth]{figures/pascals-triangle.pdf}
\end{center}

\subsection{Lucas Theorem: ${n \choose k} \mod 2$}


Something interesting happens when we take the triangle modulo $2$, that is, we replace
even numbers by $0$ and odd numbers by $1$:
\begin{center}
  \includegraphics[width=0.8\textwidth]{figures/sierpinski-small.pdf}
\end{center}
If we draw a black dot for every $1$ and look at a larger section of this triangle, we get
the following pattern, known as the Sierpinski triangle:
\begin{center}
  \includegraphics[width=0.8\textwidth]{figures/sierpinski-large.pdf}
\end{center}

Note the amazing recursive structure. This suggests we should be able to 
compute ${n \choose k} \mod 2$ without actually computing ${n \choose k}$,
by somehow employing this structure. In fact, here is a cool result
by \'Edouard Lucas, which we state here in a simpler, more special version:

The set $\N_0$ comes equipped with a partial ordering $\preceq$, in which
$x \preceq y$ if for every $i$, the $\nth{i}$ least significant bit of $x$ is 
at most that of $y$. Put in a simpler way, we write $x$ and $y$ as bit strings
in binary. If their length differ, we put a bunch of $0$'s in front of the smaller number
to make both strings of equal length $d$. Then we simply compare those strings
using the usual partial ordering $\preceq$ on $\{0,1\}^d$. For example,
$3 \preceq 7$ since $011 \preceq 111$, and $5 \preceq 23$ since $00101 \preceq 10111$,
but $7 \not \preceq 8$ since $0111\not \preceq 1000$.


\begin{theorem}
  Let $n, k\in \N_0$. Then ${n \choose k}$ is odd if $k \preceq n$ and even otherwise.
  \label{theorem-lucas-2}
\end{theorem}

Note that this theorem lets us compute ${n \choose k} \mod 2$ quickly for numbers $n,k$
having millions of digits, whereas no computer on Earth has the memory to evaluate 
the formula

\begin{align*}
{n \choose k} & = \frac{n \cdot (n-1) \cdot (n-2) \cdot \dots \cdot (n-k+2) \cdot (n-k+1)}
{k \cdot (k-1) \cdot (k-2) \cdot \dots \cdot 2 \cdot 1}
\end{align*}
for values that large. Let me now walk you through a proof of this theorem. 

\begin{definition}
  For a natural number $n \in \N$, let $|n|_1$ be the number of $1$'s in the binary
  representation of $n$. For example, $|1|_1 = |2|_1 = |4|_1 = 1$ but
  $|3|_1 = 2$ and $|7|_1 = 3$. 
\end{definition}

\begin{definition}
 For a natural number $a \in \N$ define $f(a)$ as the number of times the factor
 $2$ appears in $a$. Formally,
 \begin{align*}
 f(a) := \max \{ k \ | \ 2^k \textnormal{ divides } a\} \ .
\end{align*}
For example, $f(24) = 3$ since $8$ divides $24$ but $16$ does not.
\end{definition}

\input{Ex4}

\input{Ex5-6}

\subsection{Almost Empty Rows}

One feature of the Sierpinski triangle is that some rows are almost empty. For example, row 64
has a black dot at the very left and the very right, and only white space in between. This is because
\begin{theorem}
  Let $d \in \N_0$ and $0 < k < 2^d$. Then ${2^d \choose k}$ is even.
  \label{theorem-binomial-even}
\end{theorem}
Although this theorem follows easily from Lucas' Theorem, I want you to think about an alternative proof.
Intuitively, if some number is even, then one suspects it can be proved by ``pairing things up'' perfectly.
After all, if you can prove that in a set $S$, every element can be ``married'' to another element,
you have partitioned $S$ into couples and thus $|S|$ must be even. So let's see whether
there is a proof of Theorem~\ref{theorem-binomial-even} along these lines.
This is also
valuable because it lets you practice with notions of sets and functions. \\

Consider
the set $\{0,1\}^d$. You can view this as the set of all binary strings of length $d$.
This set has size $2^d=n$.
For $1 \leq i \leq d$ and $x \in \{0,1\}^d$ let $f_i(x)$ be $x$ with the $\nth{i}$ position
flipped. For example, $f_3(11011) = 11111$.

\input{Ex8-12}

\input{Ex13-14}


\end{document}
